<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>C++ Tutorial: Standard Template Library</title>
  <meta
 content="C++ Tutorial: Standard Template Library"
 name="description" />
  <meta
 content="C++ Tutorial, Standard Template Library, STL, Generic Programming, Containers, Iterators, Algorithms, Vectors, Lists, Deques"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right">
<a href="../gif.html">Gif</a> 
|<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../Algorithms/algorithms.html">Algorithms</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
| <a href="../python/pytut.html">Python</a> 
| <a href="../CSharp/.netframework.html">C#</a>
| <a href="../forums.html">Forums</a>
| <a href="../VisualBasicSQL/introduction.html">Visual Basic</a>
</div>
</div>

<div id="contenttext">

<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>

<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>
<br />
<br />
<br />
<br />
<div style="padding: 10px;"><span class="titletext">C++ Tutorial - Standard Template Library</span></div>
<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>   
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="stl4_algorithms.html">Standard Template Library (STL) IV - Algorithms</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>
</div>

<br /><br />
<img src="images/stl1/DuckArmSan.png" alt="DuckArmSan"/>
<br /><br />


<div class="bodytext" style="padding: 12px;" align="justify">
<div class="subtitle" id="stl">Standard Template Library (STL)</div>
<p>The Standard Template Library (STL) is the heart of the C++ standard library. There is no official definition of the STL, however, generally accepted definition may be this:<br />
The STL is the parts of C++ Standard Library what work with <strong>iterators</strong>.</p>
<p>So, it includes the <strong>containers</strong>, part of the <strong>iostream libraries</strong>, <strong>function objects</strong>, and <strong>algorithms</strong>.</p>
<p>The STL is an example of <strong>generic</strong> programming. While the <strong>object-oriented</strong> programming concentrates on the <strong>data aspect</strong> of programming, <strong>generic</strong> programming concentrates on <strong>algorithms</strong>. </p>
<p>A goal of generic programming is to write code that is <strong>independent of data types</strong>. Templates are the C++ tools for creating generic program. Templates let us define a function or class in terms of a generic type. The STL goes further by providing a generic representation of <strong>algorithms</strong>.</p>
<br />
<br />
<div class="subtitle" id="stlcomponent">STL Component</div>
<ul>
	<li><strong>Containers</strong> <br />
	Containers manage collection of element. To meet different needs, the STL provides different kinds of containers.<br />
	<ol>
		<li><strong>Sequential containers</strong> <br />
		These are <strong>ordered collections</strong> in which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element. These include <strong>vector</strong>, <strong>deque</strong>, and <strong>list</strong>. </li>
		<li><strong>Associative containers</strong> <br />
		These are <strong>sorted collections</strong> in which the actual position of an element depends on its value due to a sorting criterion. These include <strong>set</strong>, <strong>multiset</strong>, <strong>map</strong>, and <strong>multimap</strong>.</li>
	</ol>
	</li>
	<br />
	<li><strong>Iterators</strong> <br />
	Iterators are objects that can navigate over elements. An iterator represents a certain position in a container.
	Iterators are divided into five groups, based on the operations they support.<br />
	<ol>
		<li><strong>Input iterators</strong> <br />
		These are read-only iterators where each iterated location may be read only once. The most common manifestation of input iterator is <strong>istream_iterators</strong>.</li>
		<li><strong>Output iterators</strong> <br />
		These are write-only iterators where each iterated location may be read only once. The most common manifestation of output iterator is <strong>ostream_iterator</strong>.</li>
		<li><strong>Forward iterators</strong> <br />
		These have the capabilities of both input and output iterators, but they can read or write a single location repeatedly. They don't support <strong>operator--</strong>, so they can move only forward.</li>
		<li><strong>Bidirectional iterators</strong> <br />
		These are just like forward iterators, except they can go backward as well as forward. The standard associative containers all offer bidirectional iterators.</li>
		<li><strong>Random access iterators</strong> <br />
		These do everything bidirectional iterators do, but they also offer <strong>iterator arithmetic</strong>, i.e., the ability to jump forward or backward in a single step. <strong>vector</strong>, <strong>string</strong>, and <strong>deque</strong> each provide random access iterators.</li>
	</ol>
	</li>
	<br />
	<li><strong>Algorithms</strong> <br />
	The STL provides several standard algorithms for the processing of elements of collections. They can search, sort, modify, or simply use the element for different purpose. Algorithms use iterators. So, an algorithm has to be written only once to work with arbitrary containers because the iterator interface for iterators is common for all container types.</li>	
</ul>
<br />
<br />
<div class="subtitle_2nd" id="vector">Vectors</div>
<p>A <strong>vector</strong> manages its elements in a dynamic array. It enables random access, which means we can access each element directly with index.</p>
<p>Appending and removing elements at the end of the array is very fast. But inserting an element in the middle or at the beginning of the array takes time because all the following elements should be moved to make room for it while maintaining the order.</p>
<br />
<br />
<div class="subtitle_2nd" id="deques">Deques</div>
<p><strong>Double-ended-queue (deque)</strong> is a dynamic array that is implemented so that it can grow in both directions. So, inserting element at the end and at the beginning is fast. Inserting and elements in the middle, however, takes time because element must be moved.</p>

<br />
<br />
<div class="subtitle_2nd" id="lists">Lists</div>
<p>A <strong>list</strong> is implemented as a doubly linked list of element. In other words, each element in a list has its own segment of memory and refers to its predecessor and its successor. Lists do <strong>not</strong> provide <strong>random</strong> access. General access to an arbitrary element takes linear time and this is a lot worse than vectors and deques.</p>
<p>The advantage of a list is that the insertion or removal of an element is fast at any position. Only the links must be changed. This implies that moving an element in the middle of a list is very fast compared with moving an element in a vector or a deque.</p>

<br />
<br />
<div class="subtitle" id="vectorexample">Vectors with Iterator and Algorithms(STL)</div>
<p>The following code examples shows how the vector works with iterator and algorithms such as <strong>find()</strong> and <strong>for_each()</strong>. It also demonstrates the characteristics of string class as part of STL.</p>
<p>Coding itself is almost self explanatory:</p>
<pre>
// Palindrome: "A man a plan a canal Panama"
// Using vector, this code shows the given input is a palindrome
// It starts with an incomplete input, 
// to demonstrate some other operations of vector. 

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;string&gt;
#include &lt;iterator&gt;

using namespace std;

// print out all element separated by spaces
template &lt;class T&gt;
void showAll(T& v) {
	copy(v.begin(),v.end(),
		ostream_iterator&lt;string&gt;(cout," "));
	cout &lt;< endl;
}

// find the s1 and put s2 before s1
template &lt;class T&gt;
void insertMyWay(T& v, string s1, string s2) {
	T::iterator pos;
	for(pos = v.begin(); pos != v.end(); ++pos) {
		if(*pos == s1) {
			v.insert(pos,s2);
			break;
		}
	}	
}

// reverse characters of a string input
void reverseCharacters(string& s) {
		reverse(s.begin(),s.end());
}

int main()
{
	const int SIZE = 7;

	// create an empty vector
	vector&lt;string&gt; word;  

	// reserve memory for 7 elements
	word.reserve(SIZE);

	// append
	word.push_back("a");
	word.push_back("man");
	word.push_back("plan");
	word.push_back("canal");
	word.push_back("Panama");

	// display all elements
	showAll(word);

	// insert a string - we iterate the vector by ourselves
	insertMyWay(word,"plan","a");
	showAll(word);

	// insert a string - using STL algorithm find()
	word.insert(find(word.begin(),word.end(),"canal"),"a");
	showAll(word);

	// reverse the element - using STL algorithm reverse()
	reverse(word.begin(),word.end());
	showAll(word);

	// pass each element(string) of vector
	// then, reverseCharacters() will reverse the characters
	for_each(word.begin(),word.end(),reverseCharacters);

	showAll(word);
	return 0;
}
</pre>
<p>The output is:</p>
<pre>
a man plan canal Panama
a man a plan canal Panama
a man a plan a canal Panama
Panama canal a plan a man a
amanaP lanac a nalp a nam a
</pre>
<p>We could have done more to the output such as put spaces between appropriate words and convert characters to lower/upper case. Yet, it demonstrates enough use of several features that STL provides.</p>
<br />
<p>In the following Chapters, we'll look at <strong>Associative Containers</strong>, <strong>iterators</strong>, and <strong>algorithms</strong> in detail.</p>
<br />
<br />

<div class="subtitle" id="types">Types defined for STL containers</div>
<p>All STL containers define the types. In this list, we use <strong>X</strong> to represent a container type, such as 
vector&lt;double&gt;, and <strong>T</strong> for the type stored in the container, such as <strong>double</strong>.</p>
<ul>
  <li><strong>X::value_type</strong> - 
  <strong>T</strong>, the element type. <br />
  <strong>T</strong> is the type we get when the iterator is dereferenced.<br />
  For sets and multisets, it is constant. <br />
  For maps and multimaps, it is <strong>pair&lt;const key-type, mapped-type&gt;</strong>.
  </li>
  <li><strong>X::reference</strong> - 
  <strong>T&</strong>. 
  </li>
  <li><strong>X::const_reference</strong> - 
  <strong>const T&</strong>. 
  </li>
  <li><strong>X::iterator</strong> - 
  iterator type pointing to <strong>T</strong>, behaves like <strong>T*</strong>.
  </li>
  <li><strong>X::const_iterator</strong> - 
  iterator type pointing to <strong>const T</strong>, behaves like <strong>const T*</strong>.
  </li>
  <li><strong>X::difference_type</strong> - 
  signed integral type used to represent the distance from one iterator to another.
  </li>
  <li><strong>X::size_type</strong> - 
  unsigned integral type <strong>size_type</strong> can represent size of data objects, such as number of elements, and subscripts.
  </li>
</ul>
<br />
<br />
<br /><br />
<img src="images/stl1/NakDongKang.png" alt="NakDongKang"/>
<br /><br />

<br /><br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="stl4_algorithms.html">Standard Template Library (STL) IV - Algorithms</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>
<br /><br />




<br />


<br />
<br />
<br />


</div>
</div>
<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2011 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a>
</div>
</div>
</div>
</body>
</html>
